{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Describe the Painting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitPainting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #描述绘画结果"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个细长的画，用数轴表示。这幅画由若干有重叠的线段表示，每个线段有 <strong>独一无二</strong>&nbsp;的颜色。给你二维整数数组&nbsp;<code>segments</code>&nbsp;，其中&nbsp;<code>segments[i] = [start<sub>i</sub>, end<sub>i</sub>, color<sub>i</sub>]</code>&nbsp;表示线段为&nbsp;<strong>半开区间</strong>&nbsp;<code>[start<sub>i</sub>, end<sub>i</sub>)</code> 且颜色为&nbsp;<code>color<sub>i</sub></code>&nbsp;。</p>\n",
    "\n",
    "<p>线段间重叠部分的颜色会被 <strong>混合</strong>&nbsp;。如果有两种或者更多颜色混合时，它们会形成一种新的颜色，用一个 <strong>集合</strong>&nbsp;表示这个混合颜色。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，如果颜色&nbsp;<code>2</code>&nbsp;，<code>4</code>&nbsp;和&nbsp;<code>6</code>&nbsp;被混合，那么结果颜色为&nbsp;<code>{2,4,6}</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>为了简化题目，你不需要输出整个集合，只需要用集合中所有元素的 <strong>和</strong>&nbsp;来表示颜色集合。</p>\n",
    "\n",
    "<p>你想要用 <strong>最少数目</strong>&nbsp;不重叠 <strong>半开区间</strong>&nbsp;来 <b>表示</b>&nbsp;这幅混合颜色的画。这些线段可以用二维数组&nbsp;<code>painting</code>&nbsp;表示，其中 <code>painting[j] = [left<sub>j</sub>, right<sub>j</sub>, mix<sub>j</sub>]</code>&nbsp;表示一个&nbsp;<strong>半开区间</strong><code>[left<sub>j</sub>, right<sub>j</sub>)</code>&nbsp;的颜色 <strong>和</strong>&nbsp;为&nbsp;<code>mix<sub>j</sub></code>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，这幅画由&nbsp;<code>segments = [[1,4,5],[1,7,7]]</code>&nbsp;组成，那么它可以表示为&nbsp;<code>painting = [[1,4,12],[4,7,7]]</code>&nbsp;，因为：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li><code>[1,4)</code>&nbsp;由颜色&nbsp;<code>{5,7}</code>&nbsp;组成（和为&nbsp;<code>12</code>），分别来自第一个线段和第二个线段。</li>\n",
    "\t\t<li><code>[4,7)</code>&nbsp;由颜色 <code>{7}</code>&nbsp;组成，来自第二个线段。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回二维数组&nbsp;<code>painting</code>&nbsp;，它表示最终绘画的结果（<strong>没有</strong>&nbsp;被涂色的部分不出现在结果中）。你可以按 <strong>任意顺序</strong> 返回最终数组的结果。</p>\n",
    "\n",
    "<p><strong>半开区间&nbsp;</strong><code>[a, b)</code>&nbsp;是数轴上点&nbsp;<code>a</code> 和点&nbsp;<code>b</code>&nbsp;之间的部分，<strong>包含 </strong>点&nbsp;<code>a</code>&nbsp;且 <strong>不包含</strong>&nbsp;点&nbsp;<code>b</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/18/1.png\" style=\"width: 529px; height: 241px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>segments = [[1,4,5],[4,7,7],[1,7,9]]\n",
    "<b>输出：</b>[[1,4,14],[4,7,16]]\n",
    "<strong>解释：</strong>绘画结果可以表示为：\n",
    "- [1,4) 颜色为 {5,9} （和为 14），分别来自第一和第二个线段。\n",
    "- [4,7) 颜色为 {7,9} （和为 16），分别来自第二和第三个线段。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/18/2.png\" style=\"width: 532px; height: 219px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>segments = [[1,7,9],[6,8,15],[8,10,7]]\n",
    "<b>输出：</b>[[1,6,9],[6,7,24],[7,8,15],[8,10,7]]\n",
    "<b>解释：</b>绘画结果可以以表示为：\n",
    "- [1,6) 颜色为 9 ，来自第一个线段。\n",
    "- [6,7) 颜色为 {9,15} （和为 24），来自第一和第二个线段。\n",
    "- [7,8) 颜色为 15 ，来自第二个线段。\n",
    "- [8,10) 颜色为 7 ，来自第三个线段。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/04/c1.png\" style=\"width: 529px; height: 289px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>segments = [[1,4,5],[1,4,7],[4,7,1],[4,7,11]]\n",
    "<b>输出：</b>[[1,4,12],[4,7,12]]\n",
    "<strong>解释：</strong>绘画结果可以表示为：\n",
    "- [1,4) 颜色为 {5,7} （和为 12），分别来自第一和第二个线段。\n",
    "- [4,7) 颜色为 {1,11} （和为 12），分别来自第三和第四个线段。\n",
    "注意，只返回一个单独的线段 [1,7) 是不正确的，因为混合颜色的集合不相同。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= segments.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>segments[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= start<sub>i</sub> &lt; end<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= color<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li>每种颜色&nbsp;<code>color<sub>i</sub></code>&nbsp;互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [describe-the-painting](https://leetcode.cn/problems/describe-the-painting/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [describe-the-painting](https://leetcode.cn/problems/describe-the-painting/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,4,5],[4,7,7],[1,7,9]]', '[[1,7,9],[6,8,15],[8,10,7]]', '[[1,4,5],[1,4,7],[4,7,1],[4,7,11]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        s = defaultdict(int) #差分数组\n",
    "        for l, r, c in segments:\n",
    "            s[l] += c\n",
    "            s[r] -= c\n",
    "        \n",
    "        ans = []\n",
    "        pre, color = 0, 0 #pre: 上一区间的右端点 color: 现在区间的颜色\n",
    "        pos = sorted(s) #字典是乱序的 用sorted可以得到排好序的key\n",
    "        for i in pos:\n",
    "            if color != 0: #当前没有这段颜色\n",
    "                ans.append([pre, i, color])\n",
    "            pre = i\n",
    "            color += s[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        s = defaultdict(int)\n",
    "        for l, r, c in segments:\n",
    "            s[l] += c\n",
    "            s[r] -= c\n",
    "        \n",
    "        ans = []\n",
    "        pre, color = 0, 0\n",
    "        pos = sorted(s)\n",
    "        for i in pos:\n",
    "            if color != 0:\n",
    "                ans.append([pre, i, color])\n",
    "            pre = i\n",
    "            color += s[i]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        # 使用字典记录每个点的颜色变化\n",
    "        change = {}\n",
    "        for start, end, color in segments:\n",
    "            # 在开始位置累加颜色\n",
    "            if start not in change:\n",
    "                change[start] = 0\n",
    "            change[start] += color\n",
    "\n",
    "            # 在结束位置减去颜色\n",
    "            if end not in change:\n",
    "                change[end] = 0\n",
    "            change[end] -= color\n",
    "\n",
    "        # 将所有变化的点按顺序排序\n",
    "        points = sorted(change.keys())\n",
    "\n",
    "        # 初始化结果列表和当前颜色\n",
    "        res = []\n",
    "        curr_color = 0\n",
    "        prev_point = points[0]\n",
    "\n",
    "        # 遍历所有变化的点\n",
    "        for point in points:\n",
    "            # 如果当前颜色不为0，记录一个新的线段\n",
    "            if curr_color != 0:\n",
    "                res.append([prev_point, point, curr_color])\n",
    "\n",
    "            # 更新当前颜色\n",
    "            curr_color += change[point]\n",
    "            # 更新前一个点\n",
    "            prev_point = point\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        d = Counter()\n",
    "\n",
    "        for s, e, c in segments:\n",
    "            d[s] += c\n",
    "            d[e] -= c\n",
    "        # print(d)\n",
    "        pos = sorted(d.keys())\n",
    "        ans = []\n",
    "        s = d[pos[0]]\n",
    "        for i in range(1, len(pos)):\n",
    "            if s > 0:\n",
    "                ans.append([pos[i - 1], pos[i], s])\n",
    "            s += d[pos[i]]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        d = Counter()\n",
    "\n",
    "        for s, e, c in segments:\n",
    "            d[s] += c\n",
    "            d[e] -= c\n",
    "        pos = sorted(d.keys())\n",
    "        ans = []\n",
    "        s = 0\n",
    "        for i in range(1, len(pos)):\n",
    "            s += d[pos[i - 1]]\n",
    "            if s > 0:\n",
    "                ans.append([pos[i - 1], pos[i], s])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        cnt = defaultdict(int)\n",
    "        s = 0\n",
    "        for left, right, color in segments:\n",
    "            cnt[left] += color\n",
    "            cnt[right] -= color\n",
    "        ans = []\n",
    "        idxs = sorted(cnt.keys())\n",
    "        n = len(idxs)\n",
    "        for i in range(n - 1):\n",
    "            idx = idxs[i]\n",
    "            s += cnt[idx]\n",
    "            if s > 0:\n",
    "                ans.append([idx, idxs[i + 1] , s])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        diff = defaultdict(int)\n",
    "        for a, b, c in segments:\n",
    "            diff[a] += c\n",
    "            diff[b] -= c\n",
    "\n",
    "        ind = sorted(list(diff.keys()))\n",
    "        n = len(ind)\n",
    "        ans = []\n",
    "        cur = 0\n",
    "        for i in range(n - 1):\n",
    "            cur += diff[ind[i]]\n",
    "            if cur:\n",
    "                ans.append([ind[i], ind[i + 1], cur])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        diff = defaultdict(int)\n",
    "        for a, b, c in segments:\n",
    "            diff[a] += c\n",
    "            diff[b] -= c\n",
    "\n",
    "        ind = sorted(list(diff.keys()))\n",
    "        n = len(ind)\n",
    "        ans = []\n",
    "        cur = 0\n",
    "        for i in range(n - 1):\n",
    "            cur += diff[ind[i]]\n",
    "            if cur:\n",
    "                ans.append([ind[i], ind[i + 1], cur])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        d = defaultdict(int)\n",
    "        for st, end, color in segments:\n",
    "            d[st] += color\n",
    "            d[end] -= color\n",
    "        cur_color = 0\n",
    "        cur_pos = 0\n",
    "        ans = []\n",
    "        for i in sorted(d.keys()):\n",
    "            if cur_color:\n",
    "                ans.append([cur_pos, i, cur_color])\n",
    "            cur_color += d[i]\n",
    "            cur_pos = i\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        from collections import defaultdict # 用原始的也可以，用这个方便\n",
    "        ref = defaultdict(int)\n",
    "        for l, r, v in segments:\n",
    "            ref[l] += v # 进入l位置颜色加深v\n",
    "            ref[r] -= v # 进入r位置颜色变浅v\n",
    "        order = sorted(ref.keys()) # 根据顺序获得输出点\n",
    "        # print(ref)\n",
    "        ans = []\n",
    "        val = 0\n",
    "        for i in range(len(order)-1):\n",
    "            val += ref[order[i]] # 获得当前位置颜色\n",
    "            if val:ans.append([order[i], order[i+1], val]) # 颜色值不为0则加入答案\n",
    "        return(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        diff = defaultdict(int)\n",
    "        for a, b, c in segments:\n",
    "            diff[b] -= c\n",
    "            diff[a] += c\n",
    "        col = []\n",
    "        for k, v in diff.items():\n",
    "            col.append((k, v))\n",
    "        col.sort()\n",
    "        ans = []\n",
    "        last = c = 0\n",
    "        for cur, val in col:\n",
    "            if c: ans.append([last, cur, c])\n",
    "            last = cur\n",
    "            c += val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        diff = defaultdict(int)\n",
    "        for s, e, c in segments:\n",
    "            diff[s] += c\n",
    "            diff[e] -= c\n",
    "        ans = []\n",
    "        s = sorted(diff.items())\n",
    "        presum = 0\n",
    "        for i in range(1, len(s)):\n",
    "            presum += s[i - 1][1]\n",
    "            if presum:\n",
    "                ans.append([s[i - 1][0], s[i][0], presum])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        t=[]\n",
    "        a={}\n",
    "        ans=[]\n",
    "        for i in segments:\n",
    "            t.append(i[0])\n",
    "            t.append(i[1])\n",
    "            if i[0] in a:\n",
    "                a[i[0]]+=i[2]\n",
    "            else:\n",
    "                a[i[0]]=i[2]\n",
    "            if i[1] in a:\n",
    "                a[i[1]]-=i[2]\n",
    "            else:\n",
    "                a[i[1]]=-i[2]\n",
    "        t=sorted(list(set(t)))\n",
    "        q=t[0]\n",
    "        e=a[q]\n",
    "        for i in t[1:]:\n",
    "            if i in a:\n",
    "                if e!=0:\n",
    "                    ans.append([q,i,e])\n",
    "                e+=a[i]\n",
    "                q=i\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [0] * 100005\n",
    "        points = set()\n",
    "        right = 0\n",
    "        for a, b, c in segments:\n",
    "            diff[a] += c\n",
    "            diff[b] -= c\n",
    "            right = max(right, b)\n",
    "            points.add(a)\n",
    "            points.add(b)\n",
    "        ans = []\n",
    "        curr = 0\n",
    "        left = None\n",
    "        color = 0\n",
    "        for i in range(1, right + 1):\n",
    "            curr += diff[i]\n",
    "            if color and curr != color:\n",
    "                if color and left is not None:\n",
    "                    ans.append([left, i, color])\n",
    "                if curr:\n",
    "                    left = i\n",
    "                    color = curr\n",
    "                else:\n",
    "                    left = None\n",
    "            elif color and curr == color:\n",
    "                if i in points and left is not None:\n",
    "                    ans.append([left, i, color])\n",
    "                    left = i\n",
    "            if curr and left is None:\n",
    "                left = i\n",
    "                color = curr\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        N = 10 ** 5 + 7\n",
    "        diff = [0] * N\n",
    "        div = [0] * N\n",
    "        for l, r, v in segments:\n",
    "            diff[l] += v\n",
    "            diff[r] -= v\n",
    "            div[l] = div[r] = 1\n",
    "        ans = []\n",
    "        pre, v = -1, 0\n",
    "        for i in range(1, N):\n",
    "            if div[i]:\n",
    "                if pre != -1 and v:\n",
    "                    ans.append([pre, i, v])\n",
    "                pre = i\n",
    "            v += diff[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 离散差分 -- 空间效率更高的区间修改\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        from collections import defaultdict\n",
    "        diff = defaultdict(int)\n",
    "        for start, end, color in segments:  # 离散的差分\n",
    "            diff[start] += color\n",
    "            diff[end] -= color\n",
    "\n",
    "        diff = sorted([k,v] for k,v in diff.items())  # 这里其实包含了后天0！\n",
    "        for i in range(1, len(diff)):\n",
    "            diff[i][1] += diff[i-1][1]  # 前缀和统计\n",
    "\n",
    "        ans = []\n",
    "        for i in range(len(diff)-1):\n",
    "            if diff[i][1]:\n",
    "                ans.append([diff[i][0], diff[i+1][0], diff[i][1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        color = defaultdict(lambda: 0)\n",
    "        for l,r,c in segments:\n",
    "            color[l]+=c\n",
    "            color[r]-=c\n",
    "        axis = [[k,v] for k,v in color.items()]\n",
    "        axis.sort()\n",
    "        for i in range(1,len(axis)):\n",
    "            axis[i][1] += axis[i-1][1]\n",
    "        ans=[]\n",
    "        for i in range(len(axis)-1):\n",
    "            if axis[i][1]:\n",
    "                ans.append([axis[i][0],axis[i+1][0],axis[i][1]])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        :param segments:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(int)\n",
    "        m2 = defaultdict(int)\n",
    "        st = math.inf\n",
    "        ed = -math.inf\n",
    "        for i in segments:\n",
    "            m1[i[0]] += i[2]\n",
    "            m2[i[1]] += i[2]\n",
    "            st = min(st, i[0])\n",
    "            ed = max(ed, i[1])\n",
    "        ret = []\n",
    "        point = 0\n",
    "        cached = 0\n",
    "        for i in range(st, ed+1):\n",
    "            if i == st:\n",
    "                point = st\n",
    "                cached = m1[i]\n",
    "            elif i == ed:\n",
    "                ret.append([point, i, cached])\n",
    "            else:\n",
    "                if i in m1 or i in m2:\n",
    "                    if cached != 0:\n",
    "                        ret.append([point, i, cached])\n",
    "                    cached -= m2[i]\n",
    "                    point = i\n",
    "                    cached += m1[i]\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        events = []  # 用于存储所有的事件（起点和终点）\n",
    "\n",
    "        # 为每个线段的起点和终点创建事件\n",
    "        for start, end, color in segments:\n",
    "            events.append((start, color))\n",
    "            events.append((end, -color))\n",
    "\n",
    "        # 根据位置对事件进行排序\n",
    "        events.sort(key=lambda x: x[0])\n",
    "\n",
    "        res = []\n",
    "        total_color = 0  # 当前混合颜色的和\n",
    "        prev_position = 0  # 上一个扫描的位置\n",
    "\n",
    "        # 遍历所有事件\n",
    "        for position, color_change in events:\n",
    "            # 如果当前位置与上一个扫描的位置不同且混合颜色的和不为0，则开始一个新的区间\n",
    "            if position != prev_position and total_color != 0:\n",
    "                res.append([prev_position, position, total_color])\n",
    "\n",
    "            # 更新混合颜色的和\n",
    "            total_color += color_change\n",
    "            prev_position = position\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param segments:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(int)\n",
    "        m2 = defaultdict(int)\n",
    "        st = math.inf\n",
    "        ed = -math.inf\n",
    "        for i in segments:\n",
    "            m1[i[0]] += i[2]\n",
    "            m2[i[1]] += i[2]\n",
    "            st = min(st, i[0])\n",
    "            ed = max(ed, i[1])\n",
    "        ret = []\n",
    "        point = None\n",
    "        cached = None\n",
    "        for i in range(st, ed+1):\n",
    "            if i == st:\n",
    "                point = st\n",
    "                cached = m1[i]\n",
    "            elif i == ed:\n",
    "                ret.append([point, i, cached])\n",
    "            else:\n",
    "                if i in m1 or i in m2:\n",
    "                    if cached != 0:\n",
    "                        ret.append([point, i, cached])\n",
    "                    cached -= m2[i]\n",
    "\n",
    "                    point = i\n",
    "                    cached += m1[i]\n",
    "        return ret\n",
    "\n",
    "a = Solution()\n",
    "print(a.splitPainting([[1,7,9],[6,8,15],[8,10,7]]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        color = defaultdict(lambda: 0)\n",
    "        for l, r, c in segments:\n",
    "            color[l] += c\n",
    "            color[r] -= c\n",
    "        axis = sorted([k, v] for k, v in color.items())\n",
    "        n = len(axis)\n",
    "        for i in range(1, n):\n",
    "            axis[i][1] += axis[i - 1][1]\n",
    "        res: List[List[int]] = []\n",
    "        for i in range(n - 1):\n",
    "            if axis[i][1]:\n",
    "                res.append([axis[i][0], axis[i + 1][0], axis[i][1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        color = defaultdict(lambda: 0)\n",
    "        for l,r,c in segments:\n",
    "            color[l] += c\n",
    "            color[r] -= c\n",
    "        axis = [[k,v] for k,v in color.items()]\n",
    "        axis.sort()\n",
    "        for i in range(1,len(axis)):\n",
    "            axis[i][1] += axis[i-1][1]\n",
    "        ans=[]\n",
    "        for i in range(len(axis) - 1):\n",
    "            if axis[i][1]:\n",
    "                ans.append([axis[i][0], axis[i+1][0], axis[i][1]])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        pos=Counter()\n",
    "        for start,end,v in segments:\n",
    "            pos[start]+=v   \n",
    "            pos[end]-=v\n",
    "        s=0 \n",
    "        ans=[]\n",
    "        arr=list(sorted(pos.items()))\n",
    "        \n",
    "        for i,kv in enumerate(arr):\n",
    "            k,v=kv\n",
    "            s+=v   \n",
    "            arr[i]=[k,s]\n",
    "      #  print(arr)\n",
    "        for i in range(len(arr)-1):\n",
    "            if arr[i][1]:\n",
    "                ans.append([arr[i][0],arr[i+1][0],arr[i][1]])\n",
    "            \n",
    "            \n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        tag = {}\n",
    "        for start, end, color in segments:\n",
    "            if start not in tag:\n",
    "                tag[start] = 0\n",
    "            tag[start] += color\n",
    "            if end not in tag:\n",
    "                tag[end] = 0\n",
    "            tag[end] -= color\n",
    "        pos = [[loc, color] for loc, color in tag.items()]\n",
    "        pos.sort()\n",
    "        for i in range(1, len(pos)):\n",
    "            pos[i][1] = pos[i - 1][1] + pos[i][1]\n",
    "        ans = []\n",
    "        for j in range(len(pos)-1):\n",
    "            if pos[j][1]:\n",
    "                ans.append([pos[j][0], pos[j+1][0], pos[j][1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        # 计算每个位置对应的颜色和改变量并用哈希表存储\n",
    "        color = defaultdict(lambda: 0)\n",
    "        for l, r, c in segments:\n",
    "            color[l] += c\n",
    "            color[r] -= c\n",
    "        # 将哈希表转化为数组并按数轴坐标升序排序\n",
    "        axis = sorted([[k, v] for k, v in color.items()])\n",
    "        # 对数组求前缀和计算对应颜色和\n",
    "        n = len(axis)\n",
    "        for i in range(1, n):\n",
    "            axis[i][1] += axis[i-1][1]\n",
    "        # 遍历数组生成最终绘画结果\n",
    "        res = []\n",
    "        for i in range(n - 1):\n",
    "            if axis[i][1]:\n",
    "                res.append([axis[i][0], axis[i+1][0], axis[i][1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        # 计算每个位置对应的颜色和改变量并用哈希表存储\n",
    "        color = defaultdict(lambda: 0)\n",
    "        for l, r, c in segments:\n",
    "            color[l] += c\n",
    "            color[r] -= c\n",
    "        # 将哈希表转化为数组并按数轴坐标升序排序\n",
    "        axis = sorted([[k, v] for k, v in color.items()])\n",
    "        # 对数组求前缀和计算对应颜色和\n",
    "        n = len(axis)\n",
    "        for i in range(1, n):\n",
    "            axis[i][1] += axis[i-1][1]\n",
    "        # 遍历数组生成最终绘画结果\n",
    "        res = []\n",
    "        for i in range(n - 1):\n",
    "            if axis[i][1]:\n",
    "                res.append([axis[i][0], axis[i+1][0], axis[i][1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        color = defaultdict(int)\n",
    "        for s, e, c in segments:\n",
    "            color[s] += c\n",
    "            color[e] -= c \n",
    "        points = sorted([[k, v]for k, v in color.items()])\n",
    "\n",
    "        n = len(points)\n",
    "        for i in range(1, n):\n",
    "            points[i][1] += points[i-1][1]\n",
    "\n",
    "        res = []\n",
    "        for i in range(n - 1):\n",
    "            if points[i][1]:\n",
    "                res.append([points[i][0], points[i + 1][0], points[i][1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        # 计算每个位置对应的颜色和改变量并用哈希表存储\n",
    "        color = defaultdict(lambda: 0)\n",
    "        for l, r, c in segments:\n",
    "            color[l] += c\n",
    "            color[r] -= c\n",
    "        # 将哈希表转化为数组并按数轴坐标升序排序\n",
    "        axis = sorted([[k, v] for k, v in color.items()])\n",
    "        # 对数组求前缀和计算对应颜色和\n",
    "        n = len(axis)\n",
    "        for i in range(1, n):\n",
    "            axis[i][1] += axis[i-1][1]\n",
    "        # 遍历数组生成最终绘画结果\n",
    "        res = []\n",
    "        for i in range(n - 1):\n",
    "            if axis[i][1]:\n",
    "                res.append([axis[i][0], axis[i+1][0], axis[i][1]])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        color = defaultdict(lambda: 0)\n",
    "\n",
    "        for l, r, c in segments:\n",
    "            color[l] += c\n",
    "            color[r] -= c\n",
    "\n",
    "        axis = sorted([[k, v] for k, v in color.items()])\n",
    "\n",
    "        for i in range(1, len(axis)):\n",
    "            axis[i][1] += axis[i-1][1]\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(axis)-1):\n",
    "            if axis[i][1]:\n",
    "                res.append([axis[i][0], axis[i+1][0], axis[i][1]])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        # 计算每个位置对应的颜色和改变量并用哈希表存储\n",
    "        color = defaultdict(lambda: 0)\n",
    "        for l, r, c in segments:\n",
    "            color[l] += c\n",
    "            color[r] -= c\n",
    "        # 将哈希表转化为数组并按数轴坐标升序排序\n",
    "        axis = sorted([[k, v] for k, v in color.items()])\n",
    "        # 对数组求前缀和计算对应颜色和\n",
    "        n = len(axis)\n",
    "        for i in range(1, n):\n",
    "            axis[i][1] += axis[i-1][1]\n",
    "        # 遍历数组生成最终绘画结果\n",
    "        res = []\n",
    "        for i in range(n - 1):\n",
    "            if axis[i][1]:\n",
    "                res.append([axis[i][0], axis[i+1][0], axis[i][1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        color = collections.defaultdict(lambda: 0)\n",
    "        for l, r, c in segments:\n",
    "            color[l] += c\n",
    "            color[r] -= c\n",
    "        \n",
    "        axis = sorted([[k, v] for k, v in color.items()])\n",
    "        n = len(axis)\n",
    "        for i in range(1, n):\n",
    "            axis[i][1] += axis[i-1][1]\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(n - 1):\n",
    "            if axis[i][1]:\n",
    "                ans.append([axis[i][0], axis[i+1][0], axis[i][1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        color = defaultdict(int)\n",
    "        for i in range(len(segments)):\n",
    "            color[segments[i][0]] += segments[i][2]\n",
    "            color[segments[i][1]] -= segments[i][2]\n",
    "        color_sort = sorted([[k, v] for k, v in color.items()])\n",
    "        res = list()\n",
    "        for i in range(len(color_sort)):\n",
    "            if i != 0:\n",
    "                color_sort[i][1] += color_sort[i - 1][1]\n",
    "            if color_sort[i][1]:\n",
    "                res.append([color_sort[i][0], color_sort[i + 1][0], color_sort[i][1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        # 计算每个位置对应的颜色和改变量并用哈希表存储\n",
    "        color = defaultdict(lambda: 0)\n",
    "        for l, r, c in segments:\n",
    "            color[l] += c\n",
    "            color[r] -= c\n",
    "        # 将哈希表转化为数组并按数轴坐标升序排序\n",
    "        axis = sorted([[k, v] for k, v in color.items()])\n",
    "        # 对数组求前缀和计算对应颜色和\n",
    "        n = len(axis)\n",
    "        for i in range(1, n):\n",
    "            axis[i][1] += axis[i-1][1]\n",
    "        # 遍历数组生成最终绘画结果\n",
    "        res = []\n",
    "        for i in range(n - 1):\n",
    "            if axis[i][1]:\n",
    "                res.append([axis[i][0], axis[i+1][0], axis[i][1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        # 计算每个位置对应的颜色和改变量并用哈希表存储\n",
    "        color = defaultdict(lambda: 0)\n",
    "        for l, r, c in segments:\n",
    "            color[l] += c\n",
    "            color[r] -= c\n",
    "        # 将哈希表转化为数组并按数轴坐标升序排序\n",
    "        axis = sorted([[k, v] for k, v in color.items()])\n",
    "        # 对数组求前缀和计算对应颜色和\n",
    "        n = len(axis)\n",
    "        for i in range(1, n):\n",
    "            axis[i][1] += axis[i-1][1]\n",
    "        # 遍历数组生成最终绘画结果\n",
    "        res = []\n",
    "        for i in range(n - 1):\n",
    "            if axis[i][1]:\n",
    "                res.append([axis[i][0], axis[i+1][0], axis[i][1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        arr=[0]*(10**5+2)\n",
    "        starts=set()\n",
    "        for start,end,v in segments:\n",
    "            arr[start]+=v  \n",
    "            arr[end]-=v \n",
    "            starts.add(start)\n",
    "         \n",
    "        s=0\n",
    "        ans=[]\n",
    "        l=0\n",
    "        pv=0\n",
    "        for i,e in enumerate(arr):\n",
    "            s+=e  \n",
    "            arr[i]=s\n",
    "       # print(arr)\n",
    "        for r in range(1,len(arr)):\n",
    "            if arr[r-1]!=arr[r] or r in starts:\n",
    "                if arr[l]>0:\n",
    "                    ans.append([l,r,arr[l]])\n",
    "                l=r   \n",
    "            \n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "      N=100010\n",
    "      arr=[0]*N\n",
    "      visited=set()\n",
    "\n",
    "      for s,e,m in segments:\n",
    "        arr[s]+=m\n",
    "        arr[e]-=m\n",
    "        visited.add(s)\n",
    "        visited.add(e)\n",
    "      \n",
    "      res=[]\n",
    "      pre=None\n",
    "      # 判断\n",
    "      for i in range(1,N):\n",
    "        arr[i]+=arr[i-1]\n",
    "        if i in visited:\n",
    "          if pre and arr[pre]:\n",
    "            res.append([pre,i,arr[pre]])\n",
    "          pre=i\n",
    "      return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        segs = set()\n",
    "        for s, e, c in segments:\n",
    "            segs.add(s)\n",
    "            segs.add(e)\n",
    "        segs = sorted(segs)\n",
    "        n = segs[-1]\n",
    "        diff = [0]*(n+1)\n",
    "        for s,e,c in segments:\n",
    "            diff[s] += c\n",
    "            if(e <= n):\n",
    "                diff[e] -= c \n",
    "        nums = [diff[0]]\n",
    "        for i in range(1,len(diff)):\n",
    "            nums.append(nums[-1]+diff[i])\n",
    "        result = []\n",
    "        for i in range(len(segs)-1):\n",
    "            if(nums[segs[i]] == 0):\n",
    "                continue\n",
    "            result.append([segs[i],segs[i+1],nums[segs[i]]])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        segs = set()\n",
    "        for s, e, c in segments:\n",
    "            segs.add(s)\n",
    "            segs.add(e)\n",
    "        segs = sorted(segs)\n",
    "        n = segs[-1]\n",
    "        diff = [0]*(n+1)\n",
    "        for s,e,c in segments:\n",
    "            diff[s] += c\n",
    "            if(e <= n):\n",
    "                diff[e] -= c \n",
    "        nums = [diff[0]]\n",
    "        for i in range(1,len(diff)):\n",
    "            nums.append(nums[-1]+diff[i])\n",
    "        result = []\n",
    "        for i in range(len(segs)-1):\n",
    "            if(nums[segs[i]] == 0):\n",
    "                continue\n",
    "            result.append([segs[i],segs[i+1],nums[segs[i]]])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        N = 10**5 + 1\n",
    "        arr = [0] * N\n",
    "        seen = set()\n",
    "        for l, r, k in segments:\n",
    "            arr[l] += k\n",
    "            arr[r] -= k\n",
    "            seen.add(l)\n",
    "            seen.add(r)\n",
    "\n",
    "        first = 0\n",
    "        ans = []\n",
    "        for i in range(1, N):\n",
    "            arr[i] += arr[i - 1]\n",
    "            if i in seen:  # i 是端点之一\n",
    "                if first and arr[first]:  # 有前端点\n",
    "                    ans.append([first, i, arr[first]])\n",
    "                first = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [0]*(int(1e5)+1)\n",
    "        pref = [0]\n",
    "        flag = [0]*(int(1e5)+1)\n",
    "        for start, end, color in segments:\n",
    "            diff[start] += color\n",
    "            diff[end] -= color\n",
    "\n",
    "            # key point\n",
    "            if diff[start] == 0:\n",
    "                flag[start] = 1\n",
    "            if diff[end] == 0:\n",
    "                flag[end] = 1\n",
    "\n",
    "        for i in range(1,len(diff)):\n",
    "            pref.append(pref[-1]+diff[i])\n",
    "\n",
    "        ans = []\n",
    "        i = 1\n",
    "        while i<1e5:\n",
    "            if pref[i] == 0:\n",
    "                i += 1\n",
    "                continue\n",
    "            j = i+1\n",
    "            while j<=1e5 and pref[i]==pref[j] and flag[j]==0:\n",
    "                j += 1\n",
    "            if j>1e5:\n",
    "                break\n",
    "            ans.append([i, j, pref[i]])\n",
    "            i = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [0]*(int(1e5)+1)\n",
    "        pref = [0]\n",
    "        flag = [0]*(int(1e5)+1)\n",
    "        for start, end, color in segments:\n",
    "            diff[start] += color\n",
    "            diff[end] -= color\n",
    "\n",
    "            # key point\n",
    "            if diff[start] == 0:\n",
    "                flag[start] = 1\n",
    "            if diff[end] == 0:\n",
    "                flag[end] = 1\n",
    "\n",
    "        for i in range(1,len(diff)):\n",
    "            pref.append(pref[-1]+diff[i])\n",
    "\n",
    "        ans = []\n",
    "        i = 1\n",
    "        while i<1e5:\n",
    "            if pref[i] == 0:  # 前缀和为0则表示当前区域没有涂到\n",
    "                i += 1\n",
    "                continue\n",
    "            j = i+1\n",
    "            while j<=1e5 and pref[i]==pref[j] and flag[j]==0:\n",
    "                j += 1\n",
    "            ans.append([i, j, pref[i]])\n",
    "            i = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        lens = max(max(s[0], s[1]) for s in segments)\n",
    "        res = [[0, 0] for _ in range(lens + 1)]\n",
    "        for start, end, color in segments:\n",
    "            res[start-1][0] += color\n",
    "            res[end-1][1] -= color\n",
    "        \n",
    "        ans = []\n",
    "        preidx, prev = 0, sum(res[0])\n",
    "        for idx in range(1, lens+1):\n",
    "            if sum(res[idx]) != 0 or res[idx][0] != 0:\n",
    "                if prev != 0:\n",
    "                    ans.append([preidx+1, idx+1, prev])\n",
    "                preidx = idx\n",
    "                prev += sum(res[idx])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(segments)\n",
    "        e = max([segments[i][1] for i in range(len(segments))])\n",
    "        lst = [0] * (e+1)\n",
    "        covered = set()\n",
    "        for i in range(len(segments)):\n",
    "            a, b, c = segments[i][0], segments[i][1], segments[i][2]\n",
    "            lst[a] += c\n",
    "            lst[b] -= c\n",
    "            covered.add(a)\n",
    "            covered.add(b)\n",
    "        presum = []\n",
    "        cur = 0\n",
    "        for i in range(len(lst)):\n",
    "            cur += lst[i]\n",
    "            presum.append(cur)\n",
    "        for i in range(1,len(presum)):\n",
    "            if i in covered:\n",
    "                now = i \n",
    "                break\n",
    "        ans=[]\n",
    "        for i in range(now + 1,len(presum)):\n",
    "            if i in covered:\n",
    "                if presum[now]!=0:\n",
    "                    ans.append([now, i, presum[now]])\n",
    "                now = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:\n",
    "        n=len(segments)\n",
    "        e=max([segments[i][1] for i in range(len(segments))])\n",
    "        lst=[0]*(e+1)\n",
    "        covered=set()\n",
    "        for i in range(len(segments)):\n",
    "            a,b,c=segments[i][0],segments[i][1],segments[i][2]\n",
    "            lst[a]+=c\n",
    "            lst[b]-=c\n",
    "            covered.add(a)\n",
    "            covered.add(b)\n",
    "        presum=[]\n",
    "        cur=0\n",
    "        for i in range(len(lst)):\n",
    "            cur+=lst[i]\n",
    "            presum.append(cur)\n",
    "        for i in range(1,len(presum)):\n",
    "            if i in covered:\n",
    "                now=i \n",
    "                break\n",
    "        \n",
    "        ans=[]\n",
    "        \n",
    "        for i in range(now+1,len(presum)):\n",
    "            if i in covered:\n",
    "                if presum[now]!=0:\n",
    "                    ans.append([now,i,presum[now]])\n",
    "                now=i\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
